package Graph;

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class Prim {
    public static void main(String[] args) {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");
        Vertex v7 = new Vertex("v7");

        v1.edges = List.of(new Edge(v2, 2), new Edge(v3, 4), new Edge(v4, 1));
        v2.edges = List.of(new Edge(v1, 2), new Edge(v5, 10), new Edge(v4, 3));
        v3.edges = List.of(new Edge(v1, 4), new Edge(v6, 5), new Edge(v4, 2));
        v4.edges = List.of(new Edge(v1, 1), new Edge(v3, 2), new Edge(v2, 3), new Edge(v5, 7), new Edge(v7, 4), new Edge(v6, 8));
        v5.edges = List.of(new Edge(v2, 10), new Edge(v7, 6), new Edge(v4, 7));
        v6.edges = List.of(new Edge(v3, 5), new Edge(v7, 1), new Edge(v4, 8));
        v7.edges = List.of(new Edge(v5, 6), new Edge(v6, 1), new Edge(v4, 4));
        List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6, v7);
        prim(graph, v1);
    }

    private static void prim(List<Vertex> graph, Vertex source) {
        //创建优先队列
        PriorityQueue<Vertex> queue = new PriorityQueue<Vertex>(Comparator.comparingInt(value -> value.dist));
        //循环加入优先队列
        graph.forEach(queue::offer);
        //把起点距离设置为0
        source.dist = 0;
        while (!queue.isEmpty()) {
            //取出当前最小的
            Vertex curr = queue.peek();
            if (!curr.visited) {
                //更新操作
                updeteDist(curr, queue);
                curr.visited = true;
            }
            //移除
            queue.poll();
        }
        graph.forEach(vertex -> {
            System.out.println(vertex.name + " " + vertex.dist + " " + (vertex.prev != null ? vertex.prev.name : "null"));
        });
    }

    private static void updeteDist(Vertex curr, PriorityQueue<Vertex> queue) {
        curr.edges.forEach(v -> {
            //获取目标节点
            Vertex vertex = v.linked;
            if (!vertex.visited) {
                int i = v.weigth;
                if ( vertex.dist>i) {
                    vertex.prev=curr;
                    vertex.dist = i;
                    queue.offer(vertex);
                }
            }
        });

    }


}
